using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using NUnit.Framework;
using ProjectEuler.Core.Helpers;

namespace ProjectEuler.Core
{
    // this solution is based on some serious mathy stuff:
    // the given "Diophantine" equation is actually Pell's equation (x^2 - ny^2 = 1)
    // to get 'minimal' or 'fundamental' solutions to Pell's equation, start making a continued fraction for sqrt(n)
    // until the resulting fraction solves Pell's equation (where x is the numerator and y is the denominator)
    // so this solution is really a combination of problem 64 and problem 65
    // see: http://en.wikipedia.org/wiki/Pell's_equation (under "Fundamental solution via continued fractions"
    public class Problem66 : IProjectEulerProblem
    {
        public int Number
        {
            get { return 66; }
        }

        public string Description
        {
            get { return "Find the value of D <= 1000 in minimal solutions of x for which the largest value of x is obtained."; }
        }

        public string Answer
        {
            get { return FindMinimalXsWithCorrespondingDForPellsEquation(1000).OrderByDescending(kvp => kvp.Value).First().Key.ToString(); }
        }

        // <D,X>
        protected IDictionary<long,BigInteger> FindMinimalXsWithCorrespondingDForPellsEquation(int maxD)
        {
            var Ds = Enumerable.Range(2, maxD - 1).Where(d => !IsPerfectSquare(d)).ToList();
            var result = new Dictionary<long, BigInteger>();
            foreach (var D in Ds)
            {
                var length = 1;
                while(true)
                {
                    var frac = ConvergentFractionForIrrationalSquareRootOf(D, length);
                    if(DoesSolvePellsEquation(frac.Numerator, frac.Denominator, D))
                    {
                        result.Add(D,frac.Numerator);
                        break;
                    }
                    length++;
                }
            }
            return result;
        }

        protected bool IsPerfectSquare(int num)
        {
            var root = (int)Math.Floor(Math.Sqrt(num));
            var square = root*root;
            return num == square;
        }

        protected bool DoesSolvePellsEquation(BigInteger x, BigInteger y, BigInteger D)
        {
            return ((x*x) - (D*y*y)) == 1;
        }

        protected Fraction ConvergentFractionForIrrationalSquareRootOf(long S, int length)
        {
            var eseq = ConvergentSeriesForIrrationalSquareRootOf(S, length);
            var firstConvergent = new Fraction(eseq[0], 1);
            if (length == 1) return firstConvergent;
            var nthConvergent = new Fraction(1, eseq[length - 1]);
            for (var i = length - 2; i > 0; i--)
            {
                nthConvergent.AddTo(new Fraction(eseq[i], 1));
                nthConvergent.Reciprocate();
            }
            firstConvergent.AddTo(nthConvergent);
            return firstConvergent;
        }

        // this algorithm is taken from the "Continued fraction expansion"
        // at Wikipedia: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion
        // hence the short variable names
        protected Dictionary<long,long> ConvergentSeriesForIrrationalSquareRootOf(long S, int length)
        {
            var m = new Dictionary<long, long> { { 0, 0 } };
            var d = new Dictionary<long, long> { { 0, 1 } };
            var a = new Dictionary<long, long> { { 0, (long)Math.Floor(Math.Sqrt(S)) } };

            int n = 0;
            while (a.Count < length)
            {
                m[n + 1] = (d[n] * a[n]) - m[n];
                d[n + 1] = (S - (long)Math.Pow(m[n + 1], 2)) / d[n];
                a[n + 1] = (long)Math.Floor((Math.Sqrt(S) + m[n + 1]) / d[n + 1]);
                n++;
            }

            return a;
        }
    }

    [TestFixture]
    public class Problem66Tests : Problem66
    {
        [Test]
        public void Can_get_convergent_series_for_square_root_of_2()
        {
            var a = ConvergentSeriesForIrrationalSquareRootOf(2, 5);
            Assert.That(a.Count, Is.EqualTo(5));
            Assert.That(a[0], Is.EqualTo(1));
            Assert.That(a[1], Is.EqualTo(2));
            Assert.That(a[2], Is.EqualTo(2));
            Assert.That(a[3], Is.EqualTo(2));
            Assert.That(a[4], Is.EqualTo(2));
        }

        [Test]
        public void Can_get_convergent_fraction_for_square_root_of_2()
        {
            var a = ConvergentFractionForIrrationalSquareRootOf(2, 1);
            Assert.That(a.NumeratorLong, Is.EqualTo(1));
            Assert.That(a.DenominatorLong, Is.EqualTo(1));

            a = ConvergentFractionForIrrationalSquareRootOf(2, 2);
            Assert.That(a.NumeratorLong, Is.EqualTo(3));
            Assert.That(a.DenominatorLong, Is.EqualTo(2));
            
            a = ConvergentFractionForIrrationalSquareRootOf(2, 3);
            Assert.That(a.NumeratorLong, Is.EqualTo(7));
            Assert.That(a.DenominatorLong, Is.EqualTo(5));
        }

        [Test]
        public void Can_see_if_a_given_x_and_y_solves_Pells_equation()
        {
            // Baudhayana's solutions to Pell's equation
            var x = 17;
            var y = 12;
            Assert.That(DoesSolvePellsEquation(x,y,2), Is.True);
            x = 577;
            y = 408;
            Assert.That(DoesSolvePellsEquation(x,y,2), Is.True);
        }

        [Test]
        public void Can_find_given_Xs_for_D_less_than_or_equal_to_7()
        {
            var results = FindMinimalXsWithCorrespondingDForPellsEquation(7);
            Assert.That(results.Count, Is.EqualTo(5));
            Assert.That(results.Where(kvp => kvp.Key == 2 && kvp.Value == 3).Count(), Is.EqualTo(1));
            Assert.That(results.Where(kvp => kvp.Key == 3 && kvp.Value == 2).Count(), Is.EqualTo(1));
            Assert.That(results.Where(kvp => kvp.Key == 5 && kvp.Value == 9).Count(), Is.EqualTo(1));
            Assert.That(results.Where(kvp => kvp.Key == 6 && kvp.Value == 5).Count(), Is.EqualTo(1));
            Assert.That(results.Where(kvp => kvp.Key == 7 && kvp.Value == 8).Count(), Is.EqualTo(1));
            Assert.That(results.OrderByDescending(kvp=>kvp.Value).First().Key, Is.EqualTo(5));
        }

        [Test]
        public void Can_tell_if_a_number_is_a_perfect_square()
        {
            Assert.That(IsPerfectSquare(16), Is.True);
            Assert.That(IsPerfectSquare(15), Is.False);
            Assert.That(IsPerfectSquare(81), Is.True);
            Assert.That(IsPerfectSquare(80), Is.False);
        }
    }
}